#define _CRT_SECURE_NO_WARNINGS 1
#include<stdio.h>
int main()
{
    int a[1000000] = { 0 };
    int n = 0;
    a[0] = 1;
    a[1] = 2;
    scanf("%d", &n);
    int k = 0;
    for (int i = 2; i < 1000000; i++)
    {
        a[i] = (2 * a[i - 1] + a[i - 2]) % 32767;
    }
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &k);
        printf("%d\n", a[k - 1]);
    }
    return 0;
}